package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by Ghost on 2014/11/7 0007.
 */
public class Combination_Sum {
    public void find(int[] candidates, int target, ArrayList<List<Integer>> rst, ArrayList<Integer> r,int index,int sum){
        if(sum==target){
            rst.add(new ArrayList<Integer>(r));
            return;
        }
        else if(sum>target || index>=candidates.length)
            return;
        sum+=candidates[index];
        r.add(candidates[index]);
        find(candidates, target, rst, r, index, sum);
        r.remove(r.size()-1);
        sum-=candidates[index];
        find(candidates, target, rst, r, index+1, sum);
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        ArrayList<List<Integer>> rst = new ArrayList<List<Integer>>();
        ArrayList<Integer> r = new ArrayList<Integer>();
        find(candidates, target, rst, r, 0, 0);
        return rst;
    }
    public static void main(String[] args){
        Combination_Sum combinationSum = new Combination_Sum();
        int[] candidates = {1,2,4};
        System.out.println(combinationSum.combinationSum(candidates, 7));


    }
   }
